package com.wtgroup.demo.mianshi.算法.排序;

import java.util.Arrays;

public class ShellSort {
    /*
     * 子数组很短 & 部分有序 => 适合 插入排序
     * 
     * 递增必须保证从1开始, 这样递减时, 才能保证在最后一趟时, 间隔是1.
     * 设递增(递减)倍数为 m , 则需要考虑当前间隔小于 m 时的情况, 不能使其略过了 1 就结束了循环.
     * 所以, 简单办法就是令 m=2. 2/2=1, 1/2=0(结束)
     * 
     * 简单实践:
     * 间隔按1/2递减. 从 len/2 开始.
     */
    public static void main(String[] args) {
        int[] arr = new int[] { 2, 3, 1, 5, 6, 5, 29 };

        int h = arr.length / 2;
        // int h = 1;
        while (h >= 1) {

            for (int i = h; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i;
                while (j >= h && tmp < arr[j - h]) {
                    arr[j] = arr[j - h];
                    j -= h;
                }
                arr[j] = tmp;
            }

            h = h / 2;
        }

        System.out.println(Arrays.toString(arr));

    }

    
    // /**
    //  * 《算法》
    //  * @param a
    //  */
    // public static void sort(Comparable[] a) { // 将a[]按升序排列
    //     int N = a.length;
    //     int h = 1;
    //     while (h < N / 3)
    //         h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
    //     while (h >= 1) { // 将数组变为h有序
    //         for (int i = h; i < N; i++) { // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中
    //             for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
    //                 exch(a, j, j - h);
    //         }
    //         h = h / 3;
    //     }
    // }
}
